package algocasts;

import java.util.Stack;

public class P4_isSymmetric {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    boolean isSymmetricTree(TreeNode s, TreeNode t) {
        // 如果左右子树都非空
        if (s != null && t != null)
            return s.val == t.val   // 比较两个节点的值是否相等
                    // 比较 左节点的左子树 和 右节点的右子树
                    && isSymmetricTree(s.left, t.right)
                    // 比较 左节点的右子树 和 右节点的左子树
                    && isSymmetricTree(s.right, t.left);
        // 两个节点都为空才返回true
        else return s == null && t == null;
    }

    // 递归法
    boolean isSymmetricTreeRecursive(TreeNode root) {
        if (root == null) return true; // 如果根节点为空，直接返回true
        return isSymmetricTree(root.left, root.right); // 比较左右子树是否对称并返回结果
    }

    // 栈迭代
    boolean isSymmetricTreeIterative(TreeNode root) {
        // 如果根节点为空，直接返回true
        if (root == null) return true;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root.left); // 左右子树入栈
        stack.push(root.right);

        while (!stack.isEmpty()) { // 栈不为空循环
            // 出栈两个要比较的节点
            TreeNode l = stack.pop(), r = stack.pop();
            // 两个节点都为空，下一层循环，继续比较
            if (l == null && r == null) continue;
            // 一个为空一个不为空的情况。肯定不对称，返回false
            if (l == null || r == null) return false;
            // 两节点都不为空，但值不相等的情况，返回 false
            if (l.val != r.val) return false;
            stack.push(l.left);     // 对称的子节点入栈
            stack.push(r.right);
            stack.push(l.right);
            stack.push(r.left);
        }
        return true;
    }
}
